package Medium;

public class LC1004 {
    /**
     * 思路：确保滑动窗口内的数字全为1（包括在k允许的情况下由0翻转来的1）
     */
    public static int longestOnes(int[] nums, int k) {
        int headIdx, tailIdx, arrLength = nums.length;
        int allowance = k; // 还剩下多少0可以翻转

        // 初始化，head和tail位于1上（或翻转过的0上）
        if (k > 0) {
            headIdx = tailIdx = 0;
            if (nums[0] == 0) allowance--;
        }
        else { // k==0，head和tail移动到不为0的位置
            int i = 0;
            while (i < arrLength) {
                if (nums[i] == 0) i++;
                else break;
            }
            if (i >= arrLength) return 0; // 全为0
            else headIdx = tailIdx = i;
        }
        int length = 1, maxLength = 1;

        while (headIdx < arrLength - 1) {
            headIdx++;
            if (nums[headIdx] == 0) {
                if (allowance > 0) {
                    allowance--;
                }
                else { // 移动tail直到能够释放0
                    while (nums[tailIdx] != 0) tailIdx++;
                    tailIdx++; // tailIdx释放一个0
                }
            }
            length = headIdx - tailIdx + 1;
            if (length > maxLength) maxLength = length;
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1};
        System.out.println(longestOnes(nums, 3));
    }
}
